Examples of methods of performing parallel processing of sorting data are disclosed in Patent Documents 1 and 2.
FIG. 1 is a diagram for describing a parallel sorting method disclosed in Patent Document 1. FIG. 2 is a block diagram showing a configuration of a parallel sorting apparatus disclosed in Patent Document 1. A parallel sorting technique disclosed in Patent Document 1 is described below with, reference to these figures.
As shown in FIG. 2, input data 81 to be sorted is inputted to a parallel sorting apparatus. Input processing for input data 81 is performed by data input processing means 92, and then the data is stored into a main storage area 95. When thread start processing means 93 starts up a thread (not shown) in a thread pool 94, the thread recursively repeats processing of reading and processing data from the main storage area 95 and then writing back the data. When sorting is completed by the recursive processing by the thread pool 94, data output processing means 97 reads the data from the main storage area 95 and then outputs the data as output data 85.
Referring to FIG. 1, input data 81 composed of 16 values is illustrated. A thread selects a key 82 for the input data 81. Here, the key 82=“10”. Then, the thread classifies the input data 81 into a data set 83 of values smaller than the key 82 and a data set 84 of values greater than or equal to the key 82, and then stores the data into the main storage area 95. As a result, the input data 81 arranged as shown in (a) is rearranged as shown in (b). When the processing of selecting a key and classifying data is recursively repeated for each data set, sorting is completed finally as shown in (d).
FIG. 3 is a diagram for describing a parallel sorting method disclosed in Patent Document 2. In the parallel sorting technique disclosed in Patent Document 2, to-be-sorted input data 101 given as shown in (a) is divided into a plurality of parts as shown in (b) in correspondence to a plurality of processors. Here, four processors referred to as processors 0 to 3 are assumed.
Each of the processors 0 to 3 sorts data in an assigned part. As a result, the data 102 shown in (b) is rearranged into the data 103 shown in (c). Then, the plurality of processors 0 to 3 merge data sets within each part where sorting has been completed. Here, the part corresponding to the processor 0 is merged with the part corresponding to the processor 1, while the part corresponding to the processor 2 is merged with the part corresponding to the processor 3. As a result, the data 103 shown in (c) is rearranged into the data 104 shown in (d). When this processing of sorting and merging is repeated recursively, sorting is completed finally as shown in (e).    Patent Document 1: Japanese Patent Laid-Open Publication No. 2005-18158 (pages 7 to 12, FIG. 1)    Patent Document 2: Japanese Patent No. 3415914 (pages 4 to 5, FIG. 1)